// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-04-14 14:57
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DigitalDP;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.List;

public class atMostNGivenDigitSet {
    /**
     * 最大为N的数字组合
     */
    int[] nums;

    int dp(int x) {
        // 记录给定数每一位上的数字
        List<Integer> list = new ArrayList<>();
        while (x != 0) {
            list.add(x % 10);
            x /= 10;
        }
        int n = list.size(), m = nums.length, ans = 0;
        // 位数和 x 相同
        for (int i = n - 1, p = 1; i >= 0; i--, p++) {
            // 传入数字x当前数位的数字cur
            int cur = list.get(i);
            int l = 0, r = m - 1;
            // 进行二分查找匹配项
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (nums[mid] <= cur) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            // 三种情况只有等于的时候不需要使用break语句
            if (nums[r] > cur) {
                // 说明数组不存在小于cur的数字
                break;
            } else if (nums[r] == cur) {
                // p记录了当前位数的个数
                ans += r * (int) Math.pow(m, (n - p));
                // 到达树的最右边
                if (i == 0) {
                    ans++;
                }
            } else if (nums[r] < cur) {
                ans += (r + 1) * (int) Math.pow(m, (n - p));
                break;
            }
        }
        // 位数比 x 少的
        for (int i = 1, last = 1; i < n; i++) {
            int cur = last * m;
            ans += cur;
            last = cur;
        }
        return ans;
    }

    public int atMostNGivenDigitSet(String[] digits, int max) {
        int n = digits.length;
        nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.parseInt(digits[i]);
        }
        return dp(max);
    }

    @Test
    public void shout() {
//        String[] digits = {"1", "3", "5", "7"};
//        int n = 100;
        String[] digits = {"3", "4", "8"};
        int n = 4;
        System.out.println(atMostNGivenDigitSet(digits, n));
    }


}
